// Copyright (c) 2005-2008, Simon Howard
// Permission to use, copy, modify, and/or distribute this software
// for any purpose with or without fee is hereby granted, provided
// that the above copyright notice and this permission notice appear
// in all copies.
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
// WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
// WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
// AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR
// CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
// NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

use std::cmp::Ordering;
use std::fmt::Debug;
use std::ptr;

/// A doubly-linked list entry.
pub struct ListEntry<T> {
    data: T,
    prev: *mut ListEntry<T>,
    next: *mut ListEntry<T>,
}

/// A doubly-linked list.
pub struct LinkedList<T> {
    head: *mut ListEntry<T>,
}

impl<T> LinkedList<T> {
    /// Creates a new empty list.
    pub fn new() -> Self {
        LinkedList { head: ptr::null_mut() }
    }

    /// Frees the entire list.
    pub fn free(&mut self) {
        let mut entry = self.head;
        while !entry.is_null() {
            unsafe {
                let next = (*entry).next;
                Box::from_raw(entry);
                entry = next;
            }
        }
        self.head = ptr::null_mut();
    }

    /// Prepends a new entry to the list.
    pub fn prepend(&mut self, data: T) {
        let new_entry = Box::into_raw(Box::new(ListEntry {
            data,
            prev: ptr::null_mut(),
            next: self.head,
        }));

        if !self.head.is_null() {
            unsafe {
                (*self.head).prev = new_entry;
            }
        }
        self.head = new_entry;
    }

    /// Appends a new entry to the list.
    pub fn append(&mut self, data: T) {
        let new_entry = Box::into_raw(Box::new(ListEntry {
            data,
            prev: ptr::null_mut(),
            next: ptr::null_mut(),
        }));

        if self.head.is_null() {
            self.head = new_entry;
        } else {
            let mut rover = self.head;
            while !unsafe { (*rover).next }.is_null() {
                rover = unsafe { (*rover).next };
            }
            unsafe {
                (*rover).next = new_entry;
                (*new_entry).prev = rover;
            }
        }
    }

    /// Returns the data of the nth entry.
    pub fn nth_data(&self, n: usize) -> Option<&T> {
        self.nth_entry(n).map(|entry| unsafe { &(*entry).data })
    }

    /// Returns the nth entry in the list.
    fn nth_entry(&self, n: usize) -> Option<*mut ListEntry<T>> {
        let mut entry = self.head;
        for _ in 0..n {
            if entry.is_null() {
                return None;
            }
            entry = unsafe { (*entry).next };
        }
        Some(entry)
    }

    /// Returns the length of the list.
    pub fn length(&self) -> usize {
        let mut length = 0;
        let mut entry = self.head;
        while !entry.is_null() {
            length += 1;
            entry = unsafe { (*entry).next };
        }
        length
    }

    /// Converts the list to an array.
    pub fn to_array(&self) -> Vec<&T> {
        let mut array = Vec::new();
        let mut rover = self.head;
        while !rover.is_null() {
            array.push(unsafe { &(*rover).data });
            rover = unsafe { (*rover).next };
        }
        array
    }

    /// Removes an entry from the list.
    pub fn remove_entry(&mut self, entry: *mut ListEntry<T>) -> bool {
        if entry.is_null() {
            return false;
        }

        unsafe {
            if (*entry).prev.is_null() {
                self.head = (*entry).next;
            } else {
                (*(*entry).prev).next = (*entry).next;
            }

            if !(*entry).next.is_null() {
                (*(*entry).next).prev = (*entry).prev;
            }

            Box::from_raw(entry);
        }
        true
    }

    /// Removes entries matching the given data.
    pub fn remove_data<F>(&mut self, callback: F, data: &T) -> usize
    where
        F: Fn(&T, &T) -> bool,
    {
        let mut entries_removed = 0;
        let mut rover = self.head;
        while !rover.is_null() {
            let next = unsafe { (*rover).next };
            if callback(&unsafe { (*rover).data }, data) {
                self.remove_entry(rover);
                entries_removed += 1;
            }
            rover = next;
        }
        entries_removed
    }

    /// Sorts the list using the given comparison function.
    pub fn sort<F>(&mut self, compare_func: F)
    where
        F: Fn(&T, &T) -> Ordering,
    {
        let new_head = Self::sort_internal(self.head, &compare_func);
        self.head = new_head;
    }

    /// Internal function for sorting the list.
    fn sort_internal(
        list: *mut ListEntry<T>,
        compare_func: &dyn Fn(&T, &T) -> Ordering,
    ) -> *mut ListEntry<T> {
        if list.is_null() || unsafe { (*list).next }.is_null() {
            return list;
        }

        let pivot = list;
        let mut less_list = ptr::null_mut();
        let mut more_list = ptr::null_mut();
        let mut rover = unsafe { (*pivot).next };

        while !rover.is_null() {
            let next = unsafe { (*rover).next };
            if compare_func(&unsafe { (*rover).data }, &unsafe { (*pivot).data }) == Ordering::Less {
                unsafe {
                    (*rover).next = less_list;
                    (*rover).prev = ptr::null_mut();
                    if !less_list.is_null() {
                        (*less_list).prev = rover;
                    }
                    less_list = rover;
                }
            } else {
                unsafe {
                    (*rover).next = more_list;
                    (*rover).prev = ptr::null_mut();
                    if !more_list.is_null() {
                        (*more_list).prev = rover;
                    }
                    more_list = rover;
                }
            }
            rover = next;
        }

        let less_list_end = Self::sort_internal(less_list, compare_func);
        let more_list_end = Self::sort_internal(more_list, compare_func);

        let mut new_head = less_list_end;
        unsafe {
            if less_list_end.is_null() {
                new_head = pivot;
            } else {
                (*less_list_end).next = pivot;
                (*pivot).prev = less_list_end;
            }

            (*pivot).next = more_list_end;
            if !more_list_end.is_null() {
                (*more_list_end).prev = pivot;
            }
        }

        new_head
    }

    /// Finds an entry with the given data.
    pub fn find_data<F>(&self, callback: F, data: &T) -> Option<*mut ListEntry<T>>
    where
        F: Fn(&T, &T) -> bool,
    {
        let mut rover = self.head;
        while !rover.is_null() {
            if callback(&unsafe { (*rover).data }, data) {
                return Some(rover);
            }
            rover = unsafe { (*rover).next };
        }
        None
    }
}

impl<T> Drop for LinkedList<T> {
    fn drop(&mut self) {
        self.free();
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_prepend() {
        let mut list = LinkedList::new();
        list.prepend(1);
        list.prepend(2);
        assert_eq!(list.nth_data(0), Some(&2));
        assert_eq!(list.nth_data(1), Some(&1));
    }

    #[test]
    fn test_append() {
        let mut list = LinkedList::new();
        list.append(1);
        list.append(2);
        assert_eq!(list.nth_data(0), Some(&1));
        assert_eq!(list.nth_data(1), Some(&2));
    }

    #[test]
    fn test_length() {
        let mut list = LinkedList::new();
        list.append(1);
        list.append(2);
        assert_eq!(list.length(), 2);
    }

    #[test]
    fn test_to_array() {
        let mut list = LinkedList::new();
        list.append(1);
        list.append(2);
        let array = list.to_array();
        assert_eq!(array, vec![&1, &2]);
    }

    #[test]
    fn test_remove_entry() {
        let mut list = LinkedList::new();
        list.append(1);
        let entry = list.nth_entry(0).unwrap();
        assert!(list.remove_entry(entry));
        assert_eq!(list.length(), 0);
    }

    #[test]
    fn test_remove_data() {
        let mut list = LinkedList::new();
        list.append(1);
        list.append(2);
        list.append(1);
        let removed = list.remove_data(|a, b| a == b, &1);
        assert_eq!(removed, 2);
        assert_eq!(list.length(), 1);
    }

    #[test]
    fn test_sort() {
        let mut list = LinkedList::new();
        list.append(3);
        list.append(1);
        list.append(2);
        list.sort(|a, b| a.cmp(b));
        assert_eq!(list.nth_data(0), Some(&1));
        assert_eq!(list.nth_data(1), Some(&2));
        assert_eq!(list.nth_data(2), Some(&3));
    }

    #[test]
    fn test_find_data() {
        let mut list = LinkedList::new();
        list.append(1);
        list.append(2);
        let entry = list.find_data(|a, b| a == b, &2).unwrap();
        assert_eq!(unsafe { (*entry).data }, 2);
    }
}
